import java.awt.*;
import java.util.List;

public class Test {

    //二分查找


    //0〜n-1 中缺失的数字（easy）
    public int missingNumber(int[] nums){
        int left=0, right = nums.length-1;
        while(left < right){
            int mid = left + (right - left)/2;
            if (nums[mid] == mid) left = mid + 1;
            else right = mid;
        }
        return left == nums[left] ? left+1 : left;
    }


    //搜索旋转排序数组中的最⼩值（medium）
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        int x = nums[right]; // 标记⼀下最后⼀个位置的值
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] > x) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }



    //寻找峰值
    public int peakIndexInMountainArray1(int[] arr){
        int left = 1,right = arr.length-2;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(arr[mid] > arr[mid - 1]) left = mid;
            else right = mid - 1;
        }
        return left;
    }



    //山峰数组的峰顶
    public int peakIndexInMountainArray(int[] arr){
        int left = 1,right = arr.length-2;
        while(left < right){
            int mid = left + (right - left + 1)/2;
            if (arr[mid] >arr[mid-1])  left = mid;
            else right = mid - 1;
        }
        return left;
    }



    //x的平方根
    public int mySqrt(int x){
        if (x<1) return 0;
        long left = 1,right = x;
        while(left<right){
            long mid = left+(right-left+1)/2;
            if (mid*mid <= x) left = mid;
            else right = mid-1;
        }
        return (int)left;
    }



    //搜索插入位置
    public int searchInsert(int[] nums, int target){
        int left = 0,right = nums.length-1;
        while(left < right){
            int mid = left + (right -left)/2;
            if (nums[mid] < target) left = mid +1;
            else right = mid;
        }

        if (nums[right] < target) return right+1;
        return right;
    }




    //在排序数组中查找元素的第⼀个和最后⼀个位置（medium）
    public int[] searchRange(int[] nums, int target){
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        if (nums.length == 0) return ret;

        int left = 0,right = nums.length-1;
        while(left <right) {
            int mid = left +(right -left)/2;
            if (nums[mid] <target) left = mid+1;
            else right = mid;
        }

        if (nums[left] != target) return ret;
        else ret[0] = right;

        left = 0;right = nums.length-1;
        while(left<right){
            int mid = left +(right -left +1)/2;
            if (nums[mid] <= target){
                left = mid;
            }
            else{
                right = mid - 1;
            }
        }
        ret[1] = left;
        return ret;

    }



    //二分查找
    public static int search(int[] nums, int numsSize, int target)
    {
        // 初始化 left 与 right 指针
        int left = 0, right = numsSize - 1;
        // 由于两个指针相交时，当前元素还未判断，因此需要取等号
        while (left <= right)
        {
            // 先找到区间的中间元素
            int mid = left + (right - left) / 2;
            // 分三种情况讨论
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        // 如果程序⾛到这⾥，说明没有找到⽬标值，返回 -1
        return -1;
    }

}
